package leetcode.problems;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by gmwang on 2020/2/6
 * Longest Harmonious Subsequence
 * 最长和谐子序列
 */
public class LongestHarmoniousSubsequence {
    /**
     * We define a harmounious array as an array where the difference between its maximum value and its minimum value is exactly 1.
     * <p>
     * Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
     * <p>
     * Example 1:
     * <p>
     * Input: [1,3,2,2,5,2,3,7]
     * Output: 5
     * Explanation: The longest harmonious subsequence is [3,2,2,2,3].
     * <p>
     * <p>
     * Note: The length of the input array will not exceed 20,000.
     *
     * @return
     */
    public int findLHS(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int result = 0;
        for (int num: nums) {
            count.put(num, count.getOrDefault(num, 0)+1);
            result = Math.max(result, Math.max(count.getOrDefault(num-1, Integer.MIN_VALUE), count.getOrDefault(num+1, Integer.MIN_VALUE)) + count.get(num));
        }
        return result;
    }

    @Test
    public void Test() {
        int[] arr2 = {1, 3, 2, 2, 5, 2, 3, 7};
//        int[] arr2 = {1, 1, 1, 1, 3};
//        int[] arr2 = {-1,0,-1,0,-1,0,-1};
//        int[] arr2 = {1,4,1,3,1,-14,1,-13};
//        int[] arr2 = {1,3,1,3,2,3,0,3,0,1,2,2,2,-1,2,1,0,0,2,2,3,-3,1,2,2,0,1,3,1};
//        int[] arr2 = {0,3,0,0,1,1,1,3,1,3,2,3,2,3,-1,0,2,1,0,0,0,1,3,3,-3,3,3,1,3};
        int lhs = findLHS(arr2);
        System.out.println(lhs);
    }
}
